//package hot.linklist;
//
//import java.util.HashMap;
//import java.util.Map;
//
//public class A138 {
//
//}
//
//class Node {
//    int val;
//    Node next;
//    Node random;
//
//    public Node(int val) {
//        this.val = val;
//        this.next = null;
//        this.random = null;
//    }
//}
//
//class Solution {
//
//    Map<Node,Node> map=new HashMap<>();
//    public Node copyRandomList(Node head) {
//        //遍历每个节点，同时创建新节点建立新旧节点映射关系
//        Node p=head;
//        while(p!=null){
//            Node cur=new Node(p.val);
//            map.put(p,cur);
//            p=p.next;
//        }
////遍历集合
//        for (Node old : map.keySet()) {
//            map.get(old).next=map.get(old.next);
//            map.get(old).random=map.get(old.random);
//        }
//        return map.get(head);
//
//    }
//}
